#define _CRT_SECURE_NO_WARNINGS 1 

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

//线性结构的应用 --- 栈

//定义：
//	一种可以实现“先进后出”的存储结构

//分类：
//	静态栈、动态栈

//算法：
//	入栈（压栈）
//	出栈

//应用：
//	函数调用
//	中断
//	表达是求值
//	内存分配
//	缓冲处理
//	迷宫

typedef struct Node
{
	int data;
	struct Node* pNext;
}NODE, * PNODE;

typedef struct Stack
{
	PNODE pTop;//顶部
	PNODE pBottom;//底部
}STACK, * PSTACK;//PSTACK <==> struct STACK *

//函数声明
void InitStack(PSTACK );//初始化
bool Is_Empty(PSTACK pS);//判断栈内是否为空
void PushStack(PSTACK, int);//入栈（压栈）
bool PopStack(PSTACK, int*);//出栈
void Traverse(PSTACK);//遍历
void ClearStack(PSTACK);//清空栈内容（！与销毁栈有区别）


int main(void)
{
	int val = 0;
	STACK S;//STACK <==> struct Stack

	//初始化
	//目的是创建一个空栈
	InitStack(&S);

	//入栈（压栈）
	PushStack(&S, 1);
	PushStack(&S, 2);
	PushStack(&S, 3);
	PushStack(&S, 4);
	PushStack(&S, 5);
	PushStack(&S, 6);
	Traverse(&S);//遍历

	//出栈
	if (PopStack(&S, &val))
	{
		printf("出栈成功，出栈的元素是:>%d\n", val);
	}
	else
	{
		printf("出栈失败！\n");
	}
	Traverse(&S);

	//清空栈内容
	ClearStack(&S);
	Traverse(&S);

	return 0;
}

//初始化
void InitStack(PSTACK pS)
{
	pS->pTop = (PNODE)malloc(sizeof(NODE));
	if (NULL == pS->pTop)
	{
		printf("动态内存分配失败！\n");
		exit(-1);
	}
	else
	{
		pS->pBottom = pS->pTop;
		pS->pTop->pNext = NULL;//pS->Bottom->pNext = NULL;
	}
}

//判断栈内是否为空
bool Is_Empty(PSTACK pS)
{
	if (pS->pTop == pS->pBottom)//为空
	{
		return true;
	}
	else//不为空
	{
		return false;
	}
}

//入栈
void PushStack(PSTACK pS, int val)
{
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	pNew->data = val;
	pNew->pNext = pS->pTop;//pS->Top 不能改成 pS->Bottom
	pS->pTop = pNew;

	return;
}

//出栈
//把pS所指向的栈内容出栈一次，并把出栈的元素存入pVal形参所指向的变量中
//如果出栈失败，返回false.反之，返回true
bool PopStack(PSTACK pS, int* pVal)
{
	if (Is_Empty(pS))//判断栈内是否为空 && pS本身存放的就是S的地址
	{
		return false;
	}
	else
	{
		PNODE r = pS->pTop;
		*pVal = r->data;
		pS->pTop = r->pNext;
		free(r);
		r = NULL;

		return true;
	}
}


//遍历
void Traverse(PSTACK pS)
{
	PNODE p = pS->pTop;

	while (p != pS->pBottom)
	{
		printf("%d ", p->data);
		p = p->pNext;
	}
	printf("\n");

	return;
}

//清空栈内容（！与销毁栈有区别）
void ClearStack(PSTACK pS)
{
	if (Is_Empty(pS))
	{
		printf("当前栈内容为空，无需清空操作！\n");
		return ;
	}
	else
	{
		PNODE p = pS->pTop;
		PNODE q = p->pNext;

		while (p != pS->pBottom)
		{
			q = p->pNext;
			free(p);
			p = q;
		}
		pS->pTop = pS->pBottom;
		printf("清空成功！\n");
	}
}